#include<iostream>

using namespace std;

struct BinaryTreeNode {
	int value;
	BinaryTreeNode * left;
	BinaryTreeNode * right;
};

BinaryTreeNode * CreateBinaryTreeNode(int value){
    BinaryTreeNode * pHead = new BinaryTreeNode();
    pHead->value = value;
    pHead -> left = pHead -> right = nullptr;
    return pHead;
}

// connect ListNode
void ConnectTreeNodes( BinaryTreeNode * root , 
					BinaryTreeNode * left, BinaryTreeNode * right){
    root -> left = left;
	root -> right = right;
}

bool isTree1HadTree2(BinaryTreeNode * root, BinaryTreeNode * subRoot){
	if ( subRoot == nullptr )
		return true;
	if ( root == nullptr )
		return false;
	if ( root-> value == subRoot-> value ){
		return isTree1HadTree2( root -> left, subRoot->left) && isTree1HadTree2( root -> right, subRoot->right);
	}
	return false;
}

bool substructureInTree(BinaryTreeNode * root, BinaryTreeNode * subRoot){
	if ( root == nullptr || subRoot == nullptr ){
		return false;
	}
	
	bool flag = false;
	
	if ( root != nullptr && subRoot != nullptr ){
		if ( root -> value == subRoot -> value ){
			// 根节点值相等
			flag = isTree1HadTree2(root, subRoot);
		}
		if ( !flag ) flag = substructureInTree(root->left, subRoot);
		if ( !flag ) flag = substructureInTree(root->right, subRoot);
	}
	return flag;
}


void printTreeNode(BinaryTreeNode * root){
	if ( root != nullptr ){
		cout << root -> value << endl;
		printTreeNode(root->left);
		printTreeNode(root->right);
	}
}

int main(void){
	BinaryTreeNode* pNode8 = CreateBinaryTreeNode(8);
    BinaryTreeNode* pNode6 = CreateBinaryTreeNode(6);
    BinaryTreeNode* pNode10 = CreateBinaryTreeNode(10);
    BinaryTreeNode* pNode5 = CreateBinaryTreeNode(5);
    BinaryTreeNode* pNode7 = CreateBinaryTreeNode(7);
    BinaryTreeNode* pNode9 = CreateBinaryTreeNode(9);
    BinaryTreeNode* pNode11 = CreateBinaryTreeNode(11);

	// BinaryTree 1
    ConnectTreeNodes(pNode8, pNode6, pNode10);
    ConnectTreeNodes(pNode6, pNode5, pNode7);
    ConnectTreeNodes(pNode10, pNode9, pNode11);
	
	// BinaryTree 2
    ConnectTreeNodes(pNode6, pNode5, pNode7);
	
	bool result = substructureInTree(pNode8, pNode6);
	
	cout << result << endl;
	return 0;
}